import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Heap4 {
    public int[] elem;
    public int UseSize;

    public Heap4(){
        this.elem=new int[10];
    }
    public void init(int[] array){
        for (int i = 0; i < elem.length; i++) {
            elem[i]=array[i];
            UseSize++;
        }
    }
    public void createHeap(){
        for(int i=(UseSize-1-1)/2;i>0;i--){
            sitfDown(i,UseSize);
        }
    }
    public void swap(int i,int j){
        int tam=i;
        i=j;
        j=tam;
    }
    public void sitfDown(int parent,int end){
        int child=2*parent+1;
        while(child<end){
            if(child+1<end&&elem[child]<elem[child+1]){
                child++;
            }
            if(child>parent){
                swap(child,parent);
                parent=child;
                child=2*parent+1;

            }else
                break;
        }
    }

    public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[UseSize]=val;
        UseSize++;
        siftUp(UseSize-1);
    }
    public boolean isFull(){
        return UseSize==elem.length;
    }
    public void siftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent>=0){
            if(elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }
    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int old=elem[0];
        swap(0,UseSize-1);
        UseSize--;
        sitfDown(0,UseSize);
        return old;
    }
    public boolean isEmpty(){
        return UseSize==0;
    }
    class IntCmp implements Comparator<Integer>{
        public int compare(Integer o1,Integer o2){
            return o2.compareTo(o1);
        }
    }
    public int[] smallestK(int[] arr,int k){
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<Integer>(new IntCmp());
        int[] tam=new int[k];
        if(k==0){
            return tam;
        }
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length ; i++) {
            int val=priorityQueue.peek();
            if(arr[i]<val){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            tam[i]=priorityQueue.poll();
        }
        return tam;
    }
}
